个人计算机知识展示

Appearance

递归 ​

定义 ​

递归是一种编程思想，实现的效果是迭代循环，但是与普通循环不同的是，递归是靠函数调用函数自身来实现的。

所以，首先要理解和学会使用自定义函数。

递归函数

递归函数一般要包含两个部分：

  1. 结束条件（bottom cases），返回一个已知的最简单的结果，如一个具体的值，从而结束递归，而不会陷入死循环。
  2. 递推关系（recursive relation），根据递归关系，调用函数自身，一般会传入不同的参数。

示例 ​

数的阶乘

数的阶乘是指，输入一个数字 n，程序返回 n 的阶乘 n!，即 n x (n-1) x (n-2) x …… x 1。

python
#记得先在stdin里输入一个数字
def factorial(n):
    if n == 1:
        return 1 #结束条件
    return n * factorial(n-1) #递推关系
n = int(input())
result = factorial(n)
print('The factorial of',n,'is',result)

数的阶乘递归算法

递归函数其实也可以理解为数学里分段递归函数的一种程序实现。阶乘函数的数学表示方法如下:

f(x)={1(x=1)x∗f(x−1)(x>1)

对于 5 的阶乘来说，就是 f(5)依次类推，得到最终的结果是 120。

  • f(5) = 5 * f(4)
  • f(4) = 4 * f(3)
  • f(3) = 3 * f(2)
  • f(2) = 2 * f(1)
  • f(1) = 1
  • =>
  • f(5) = 5 * f(4) = 5 * 4 * f(3) = 5 * 4 * 3 * f(2) = 5 * 4 * 3 * 2 * f(1) = 5 * 4 * 3 * 2 * 1 = 120
也可以用循环结构来实现数字阶乘
python
#记得先在stdin里输入一个数字
n = int(input())
result = 1
while n > 1:
    result *= n
    n -= 1
print('The factorial of',n,'is',result)

总结 ​

分治 ​

分治，字面上的解释是“分而治之”，将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。如排序算法中（快速排序，归并排序）就属于分治算法。

分治算法重要在于理解其思想，在其它算法中也都会有分治算法的思想存在。

分治

要实现递归算法，首先应该要找出问题的递推关系，然后建立一个相应的数学模型，最后使用代码来实现这个模型，从而解决问题。

结束条件

一定要确保递归函数里有 结束条件 ，否则会陷入死循环。

递归应用

后续快速排序、归并排序、深度优先搜索（回溯法）等算法都用到了递归的思想。

练习 ​

题目来源难度
上台阶http://oj.oldmoon.cn/p/A1190容易
汉诺塔http://oj.oldmoon.cn/p/A1205容易
放苹果http://oj.oldmoon.cn/p/A1192普通
Unfriendhttp://oj.oldmoon.cn/p/CCC11J5容易
π-dayhttp://oj.oldmoon.cn/p/CCC15J5普通